There are many applications where an associative memory called a content addressable memory (CAM) is used as a look-up table that stores information that can be searched. Example look-up table applications include cache memory subsystems, network address translation, pattern recognition, data compression, and encryption. There are many types of CAM devices known in the art, but they generally follow the same principle of operation.
Generally, the CAM receives search data from the system, executes the search internally, and provides an indication if the search data has been found or not within its memory array. If the search data is found, the indication is referred to as a “hit”. Otherwise, the search data is not present in the CAM and the indication is referred to as a “miss”. The CAM can provide hit and miss signals, each corresponding to a binary state. In the case of a hit, the CAM provides a lookup index corresponding to, or associated with, the location of the matching data stored in the CAM. The lookup index is then used by the system as a pointer for accessing a location in another memory, such as a cache memory. In the case of a miss, the CAM will provide a lookup index corresponding to, or associated with, a free location in the CAM which can be used for storing data, such as the absent search data. The free location may or may not store search data. However, because there are a finite number of storage locations in the CAM, a storage location storing search data may be released to store new search data. Accordingly, any search for this new search data will yield the same lookup index. The problem arising from this is discussed later. With this understanding of the general operation of a typical CAM device, the following outlines an example system that uses a CAM device.
FIG. 1 is a block diagram of a multi-client CAM system 5 of the prior art. This system consists of one CAM device 10, any number of clients 12 (Named Client 0 to Client N) which can access CAM device 10, cache memory 14, a key fetch engine 16, and host memory 18. By example, there can be up N clients, where N can be any non-zero integer value. A client 12 can be an application or separate sub-system that requires data stored in CAM device 10. Since each client 12 can access CAM device 10 asynchronously by sending index requests, such as “Index request A”, an arbiter 11 is provided for regulating and/or controlling accesses to the CAM device 10 in accordance with any suitable algorithm that ensures fair access to the CAM device 10 by all the clients 12. For example, arbiter 11 can decide which client 12 should gain access first based on time of the request. The arbiter 11 can be a state machine implemented with logic that can be integrated within CAM device 10 or implemented as a separate circuit block. All the clients 12 can access the cache memory 14, which stores information such as key data that is pointed to by the lookup index provided by CAM device 10. All the clients 12 can instruct the key fetch engine 16 to access some other higher latency location, such as host memory 18 for example, to retrieve data that is not in the cache memory 14. Those skilled in the art should understand that cache memory 14 is intended to be a high speed and low latency storage means to improve performance of the system.
In general operation, any client 12 can send an index request (search data) to CAM device 10. If there is a hit, the corresponding lookup index is returned to the client 12 by CAM device 10 with the active logic level hit signal, which can be either a logic “1” or a logic “0”. The client 12 will then access cache memory 14 to retrieve or read the key data at the memory location pointed to by the lookup index. However, if there is a CAM lookup miss, an available lookup index is returned to client 12 with the active logic level miss signal (either logic “1” or “0”). The miss status also means that there is no corresponding key data in cache memory 14. Therefore the client 12 must execute specific algorithms for retrieving the desired key data from host memory 18, write the corresponding key data into the cache memory 14, and write the search data to CAM device 10. Those skilled in the art should understand that this is a time consuming process which degrades system performance and is the motivation for specifying a local cache in the design.
The delay between CAM index grants and the latency of updating the local cache contents in the presence of multiple requests can lead to corruption of the CAM device 10, especially in the presence of a Least Recently Used (LRU) entry eviction algorithm. In short, an LRU entry eviction algorithm is used when there are no empty storage locations in the CAM device 10 for storing new search data, thus the entry which has been tagged as being the least frequently requested is made available for storing the new search data. This means that statistically, there is a low probability for this entry in the CAM device 10 to be requested in the future, hence the entry should be made available for an entry that potentially has a higher probability to be requested. In particular, these problems occur due to the time required for populating the cache memory 14 and the search data in CAM device 10 in the event of a miss. There are at least the following specific problems in the system of FIG. 1, where there are multiple clients 12 that can make requests of a single CAM device 10.
Using the previously described example, a search request for the same search data by a second client 12 after a missed search request from a first client 12, can cause erroneous key data to be retrieved from the cache memory 14 by the second client 12. As previously mentioned, the CAM device 10 treats the second identical search request as a hit, even though the first search request resulted in a miss. Now the lookup index provided by the CAM device 10 is considered by the second client 12 to point to corresponding key data stored in the cache memory 14. Unfortunately, due to the delay of the key data fetching operation, also referred to as a memory fetch operation, from the host memory 18 initiated by the first client 12, the proper key data will not be loaded into the cache memory location in time for the second client 12. Therefore, erroneous key data will be obtained by the second client 12.
In another example, when a first client 12 receives a miss status for its search request based on Index A, it receives an available lookup index (Position X for example), and the time-intensive key fetching process from the host memory 18 is executed. However, a second client 21 can initiate multiple search requests each resulting in a hit. This can result in tagging of the newly assigned lookup index as the least recently used one. If another client 12 sends a search request differing from that of the first client 12 that results in a miss, then the CAM device 10 will assign lookup index (Position X) since it is tagged as the least recently used one. Therefore, the same available lookup index is provided to two different clients 12, even though both had misses based on different search data.
It is, therefore, desirable to provide a system and method to maximize efficient and reliable use of a single CAM by multiple clients, while preventing corruption of CAM contents in the presence of an LRU entry eviction algorithm.